//===--- BlotSetVector.h ----------------------------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_BASIC_BLOTSETVECTOR_H
#define POLARPHP_BASIC_BLOTSETVECTOR_H

#include "polarphp/basic/LLVM.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include <vector>

namespace polar {

/// This is a set container with the following properties:
///
/// 1. Fast insertion-order iteration.
///
/// 2. Stable index offsets for all values after all operations including
/// erase.
///
/// This contrasts with SetVector where index offsets are not stable due to
/// usage of std::vector::erase(). In contrast, BlotSetVector uses the `blot
/// operation' (a) which trades memory for runtime and index offset stability.
///
/// 3. Fast replacement of a value v1 with a second value v2 guaranteeing that
/// v2 is placed into the same array index as v1, just deleting v1 if v2 is
/// already in the array.
///
/// This is important if one has other data structures referring to v1 via v1's
/// index in the vector that one wishes to now refer to v2.
///
/// 4. Fast deletion via the 'blot' operation.
///
/// 5. Fast insertion.
///
/// (a) The `blot operation' is leaving the value in the set vector, but marking
/// the value as being dead.
template <typename ValueT, typename VectorT = std::vector<Optional<ValueT>>,
   typename MapT = llvm::DenseMap<ValueT, unsigned>>
class BlotSetVector {
   VectorT vector;
   MapT map;

public:
   /// Construct an empty BlotSetVector.
   BlotSetVector() {}

   bool empty() const { return vector.empty(); }

   unsigned size() const { return vector.size(); }

   using iterator = typename VectorT::iterator;
   using const_iterator = typename VectorT::const_iterator;
   iterator begin() { return vector.begin(); }
   iterator end() { return vector.end(); }
   const_iterator begin() const { return vector.begin(); }
   const_iterator end() const { return vector.end(); }

   ArrayRef<Optional<ValueT>> getArray() const { return vector; }

   llvm::iterator_range<const_iterator> getRange() const {
      return {begin(), end()};
   }

   using const_reverse_iterator = typename VectorT::const_reverse_iterator;
   const_reverse_iterator rbegin() const { return vector.rbegin(); }
   const_reverse_iterator rend() const { return vector.rend(); }
   llvm::iterator_range<const_reverse_iterator> getReverseRange() const {
      return {rbegin(), rend()};
   }

   const Optional<ValueT> &operator[](unsigned n) const {
      assert(n < vector.size() && "Out of range!");
      return vector[n];
   }

   /// Grow the set vector so that it can contain at least \p capacity items
   /// before resizing again.
   ///
   /// \param capacity The minimum size that the set vector will be able to grow
   ///                 to before a resize is required to insert additional items.
   void reserve(unsigned capacity) {
      vector.reserve(capacity);
      map.reserve(capacity);
   }

   /// Insert \p value into the SetVector if it is not there already.
   ///
   /// \param value The item to insert if not already present.
   ///
   /// \returns Both the index of the item and whether it was inserted in a pair.
   ///          If the item was already present, its preexisting index along with
   ///          false will be returned.  If the item was newly added, its new
   ///          index along with true will be returned.
   std::pair<unsigned, bool> insert(const ValueT &value) {
      auto iterator = map.find(value);
      if (iterator != map.end())
         return {iterator->second, false};

      unsigned index = vector.size();
      map[value] = index;
      vector.push_back(value);
      return {index, true};
   }

   /// Replace \p value1 with \p value2 placing \p value2 into the position in
   /// the array where value1 used to be. If \p value2 is already in the set,
   /// this just erases \p value1.
   void replace(const ValueT &value1, const ValueT &value2) {
      auto iterator1 = map.find(value1);
      assert(iterator1 != map.end() && "Cannot replace value that is not in set");
      unsigned index1 = iterator1->second;
      map.erase(value1);

      auto iterator2 = map.find(value2);
      if (iterator2 != map.end()) {
         vector[index1] = None;
         return;
      }

      map[value2] = index1;
      vector[index1] = value2;
   }

   /// Erase the value \p value if it is in the set. Returns true if value was
   /// successfully erased and false otherwise.
   bool erase(const ValueT &value) {
      auto iterator = map.find(value);
      if (iterator == map.end())
         return false;
      unsigned index = iterator->second;
      map.erase(iterator);
      vector[index] = None;
      return true;
   }

   /// Return the last element of the blot map vector. Will be None if blotted.
   Optional<ValueT> pop_back_val() {
      auto result = vector.pop_back_val();
      if (!result)
         return result;
      map.erase(*result);
      return result;
   }

   /// Attempt to lookup the index of \p value. Returns None upon failure and the
   /// value on success.
   Optional<unsigned> getIndex(const ValueT &value) {
      auto iterator = map.find(value);
      if (iterator == map.end())
         return None;
      return iterator->second;
   }

   /// Clear the backing vector and map.
   void clear() {
      vector.clear();
      map.clear();
   }
};

template <typename ValueT, unsigned N>
class SmallBlotSetVector
   : public BlotSetVector<ValueT, llvm::SmallVector<Optional<ValueT>, N>,
      llvm::SmallDenseMap<ValueT, unsigned, N>> {
public:
   SmallBlotSetVector() {}
};

} // namespace polar

#endif // POLARPHP_BASIC_BLOTSETVECTOR_H
